|
In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal. == Example == The proof that P = NP implies EXP = NEXP uses "padding". by definition, so it suffices to show . Let ''L'' be a language in NEXP. Since ''L'' is in NEXP, there is a non-deterministic Turing machine ''M'' that decides ''L'' in time for some constant ''c''. Let : where ''1'' is a symbol not occurring in ''L''. First we show that is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that ''L'' is in EXP. can be decided in non-deterministic polynomial time as follows. Given input , verify that it has the form time, which is polynomial in the size of the input, . So, is in NP. By the assumption P = NP, there is also a deterministic machine ''DM'' that decides in polynomial time. We can then decide ''L'' in deterministic exponential time as follows. Given input , simulate . This takes only exponential time in the size of the input, . The is called the "padding" of the language ''L''. This type of argument is also sometimes used for space complexity classes, alternating classes, and bounded alternating classes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「padding argument」の詳細全文を読む スポンサード リンク
|